package medium;

/**
 * 522. 最长特殊序列 II
 * 判断一个字符串是不是其他最字符串的子序列，找到不是且是最长的那个
 * 创建时间： 2024-06-16 22:45
 **/
public class 最长特殊序列II_522 {
    public int findLUSlength(String[] strs) {
        int ans = -1; //没有的话返回-1
        // 不是其他字符串的子序列，所以 字符串越长，就越不可能是其他字符串的子序列。
        next:
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].length() <= ans) {
                continue;
            }
            for (int j = 0; j < strs.length; j++) {
                if (i != j && isSubsequence(strs[i], strs[j])) {
                    continue next;
                }
            }
            ans = strs[i].length();
        }
        return ans;
    }

    /**
     * 判断 s 是否为 t 的子序列
     */
    public boolean isSubsequence(String s, String t) {
        if (s.isEmpty()) {
            return true;
        }
        if (s.length() > t.length()) {
            return false;
        }
        int i = 0;
        for (char c : t.toCharArray()) {
            if (s.charAt(i) == c && ++i == s.length()) {
                return true;
            }
        }
        return false;
    }
}
